package ch.ams.fhnw.sudoku;




public class SudokuSolver {
	
	private long solveTime;
	private long iterations;
	private final int[][] data;
	private int[][] result;
	private boolean solutionFound;
	
	public SudokuSolver(int[][] data) {
		if(data == null || data.length != 9 || data[0].length != 9) {
			throw new IllegalStateException("incorrect sudoku data format");
		}
		
		this.data = data;
		result = null;
	}
	
	public void solve() {
		long startTime = System.currentTimeMillis();
		
		solve(copyData(data), 0, 0);
		
		if (result == null) {
			solutionFound = false;
			result = copyData(data);
		} else {
			solutionFound = true;
		}
		
		solveTime = System.currentTimeMillis() - startTime;
	}
	
	public boolean validate() {
		boolean ret = false;

		if (checkEachRow(data) && checkEachColumn(data) && checkAllBlocks(data)) {
			ret = true;
		}

		return ret;
	}
	
	private void solve(int[][] data, int row, int column) {
		iterations++;
		int nextRow = 0;
		int nextColumn = 0;

		// index empty
		if (data[row][column] == 0) { 

			// check all possible numbers for index
			for (int possibleNumber = 1; possibleNumber < 10; possibleNumber++) {
				data[row][column] = possibleNumber;

				//check sudoku rules
				if (checkRow(data, row) && checkColumn(data, column)
						&& checkAllBlocks(data) && result == null) {
					
					if (row == 8 && column == 8) {
						result = copyData(data); //result found
						return;
					}

					// next iteration
					if (column == 8) {
						nextRow = row + 1;
						nextColumn = 0;
					} else {
						nextRow = row;
						nextColumn = column + 1;
					}
					solve(copyData(data), nextRow, nextColumn); 
				}
			}
			return; // no possible number found
		}
		
		if (row == 8 && column == 8) {
			result = copyData(data); // result found
			return;
		}

		//next iteration
		if (column == 8) {
			nextRow = row + 1;
			nextColumn = 0;
		} else {
			nextRow = row;
			nextColumn = column + 1;
		}
		solve(data, nextRow, nextColumn); 
	}

	private int[][] copyData(int[][] data) {
		int[][] copy = new int[9][9];
		
		for(int column = 0; column < 9; column++) {
			for (int row = 0; row < 9; row++) {
				copy[row][column] = data[row][column];
			}
		}
		
		return copy;
	}
	
//	private int[][] copyData(final int[][] data) {
//		int[][] copy = data.clone();
//		
//		return copy;
//	}
	
	private boolean checkEachRow(int[][] data) {
		boolean ret = true;
		
		for(int row = 0; row < data.length ; row++) {
			if(!checkRow(data, row)) {
				ret = false;
			}
		}
		
		return ret;
	}
	
	/**
	 * 
	 * @return true = sudoku rule ok  false = duplicated number in row
	 */
	private boolean checkRow(int[][] data, int row) {
		boolean ret = true;
			
			for (int column1 = 0; column1 < data.length; column1++) {
				for (int column2 = 0;  column2 < data.length; column2++) {
					if(column1 == column2) {
						continue; //same index
					}
					int num1 = data[row][column1];
					int num2 = data[row][column2];
					
					if(num1 == num2 && num1 > 0 && num2 > 0) {
						ret = false; 
					}
				}
		}
		
		return ret;
	}
	
	private boolean checkEachColumn(int[][] data) {
		boolean ret = true;
		
		for(int column = 0; column < data[0].length ; column++) {
			if(!checkColumn(data, column)) {
				ret = false;
			}
		}
		
		return ret;
	}
	
	/**
	 * 
	 * @return true = sudoku rule ok  false = duplicated number in column
	 */
	private boolean checkColumn(int[][] data, int column) {
		boolean ret = true;
			
			for (int row1 = 0; row1 < data[0].length; row1++) {
				for (int row2 = 0;  row2 < data[0].length; row2++) {
					if(row1 == row2) {
						continue; //same index
					}
					int num1 = data[row1][column];
					int num2 = data[row2][column];
					
					if(num1 == num2 && num1 > 0 && num2 > 0) {
						ret = false; 
					}
				}
		}
		return ret;
	}
	
	private boolean checkAllBlocks(int[][] data) {
		boolean ret = true;
		
		for(int block = 0; block < data[0].length ; block++) {
			if(!checkBlock(data, block)) {
				ret = false;
			}
		}
		
		return ret;
	}
	
	/**
	 * 
	 * @param block number of block, from 0 to 8, from upper left to lower right
	 * @return
	 */
	private boolean checkBlock(int [][] data, int blockNum) {
		boolean ret = true;
		int[] sudokuBlock = getBlock(data, blockNum);
		
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if(i == j) {
					continue; //ignore same index
				}
				int num1 = sudokuBlock[i];
				int num2 = sudokuBlock[j];
				
				if(num1 == num2 && num1 > 0 && num2 > 0) {
					ret = false; 
				}
			}
		}
		
		return ret;
	}
	
	/**
	 * 
	 * @param blockNum
	 *            number of block, from 0 to 8, from upper left to lower right
	 * @return sudoku block
	 */
	private int[] getBlock(int [][] data, int blockNum) {
		int[] block = new int[9];
		int offsetX = 0;
		int offsetY = 0;
		
		switch (blockNum) {
		case 0:
			offsetX = 0;
			offsetY = 0;
			break;
		case 1:
			offsetX = 3;
			offsetY = 0;
			break;
		case 2:
			offsetX = 6;
			offsetY = 0;
			break;
		case 3:
			offsetX = 0;
			offsetY = 3;
			break;
		case 4:
			offsetX = 3;
			offsetY = 3;
			break;
		case 5:
			offsetX = 6;
			offsetY = 3;
			break;
		case 6:
			offsetX = 0;
			offsetY = 6;
			break;
		case 7:
			offsetX = 3;
			offsetY = 6;
			break;
		case 8:
			offsetX = 6;
			offsetY = 6;
			break;
		default:
			return block; //empty block
		}
		
		int count = 0;
		for(int i = offsetY; i < (offsetY + 3); i++) { //each row
			for(int j = offsetX; j < (offsetX + 3); j++) { //each column
				block[count++] = data[i][j];
			}
		}
		
		return block;
	}
	
	public long getSolveTime() {
		return solveTime;
	}

	public long getIterations() {
		return iterations;
	}

	public int[][] getData() {
		return data;
	}
	
	public boolean hasSolution() {
		return solutionFound;
	}
	
	public int[][] getResult(){
		return result;
	}
}
